package bintree;

import java.util.NoSuchElementException;

public class MyBinSearchTree {
    private int size;
    // 当前树的树根
    private Node root;

    public void add(int val) {
        root = add(root,val);
    }
    /**
     * 向当前以root为根的BST中插入一个新元素val，返回插入后的树根
     * @param root
     * @param val
     * @return
     */
    private Node add(Node root, int val) {
        if (root == null) {
            // 此时树为空，node就是树根
            Node node = new Node(val);
            size ++;
            return node;
        }
        if (val < root.val) {
            // 此时要在左子树中插入
            root.left = add(root.left,val);
        }
        if (val > root.val) {
            // 此时在右子树中插入
            root.right = add(root.right,val);
        }
        return root;
    }

    public boolean contains(int val) {
        return contains(root,val);
    }

    /**
     * 判断以当前root为根的BST中是否包含指定值val，存在返回true，否则返回false
     * @param root
     * @param val
     * @return
     */
    private boolean contains(Node root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        else if (val < root.val) {
            return contains(root.left,val);
        }else {
            return contains(root.right,val);
        }
    }
    //BST中找到最小值节点
    public  int findMin(){
        if (size==0){
            throw new NoSuchElementException("bst is empty !no element");
        }
        return min(root).val;
    }

    public int removeMin() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        Node minNode = min(root);
        root = removeMin(root);
        return minNode.val;
    }


    //传入以root为根的BST就能删除其中最小值，返回删除后的树根结点；
    public Node removeMin(Node root){
        if (root.left==null){
            Node right = root.right;
            root.left=root.right=root=null;
            size--;
            return right;
        }
        root.left= removeMin(root.left);
        return root;
    }

    private Node min(Node root){
        if (root.left==null){
            return root;
        }
        return min(root.left);
    }
//BST中找到最大值节点
    public  int findMax(){
        if (size==0){
            throw new NoSuchElementException("bst is empty !no element");
        }
        return max(root).val;
    }

    public  int remveMax(){
        if (size == 0){
            throw new NoSuchElementException("bst is empty !no element");
        }
        Node max = max(root);
        root = remveMax(root);
        return max.val;
    }

    //删除以root为跟的BST中的最大值结点，返回删除后的树根结点


    private Node remveMax(Node root) {
        if (root.right==null){
            Node left = root.left;
            root.left=root.right=root=null;
            size--;
            return left;
        }
        root.right= removeMin(root.right);
        return root;
    }

    private Node max(Node root){
        if (root.right==null){
            return root;
        }
        return min(root.right);
    }

    public void remove(int val) {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        root = remove(root,val);
    }



    //在当前以root为根的BST中删除值为VAL的结点，返回删除后的新的树根结点
    private Node remove(Node root, int val){
            if (root == null) {
                // 将树中所有节点全都遍历一遍以后还没找到值为val的结点，节点根本不存在！
                throw new NoSuchElementException("bst has not this node!");
            }else if (val<root.val){
                //在左子树中删除
                root.left=remove(root.left,val);
                return root;
            }else if(val>root.val){
                root.right = remove(root.right,val);
                return root;
            }else {
                // 树不为空，且root.val == val
                // 当前root就是待删除的节点
                if (root.left==null){
                    // 当前待删除节点的左树为空，类似删除最小值,返回右子树的树根
                    Node right = root.right;
                    root.right=root=null;
                    size--;
                    return right;
                }
                if (root.right==null){
                    Node left = root.left;
                    root.left=root=null;
                    size--;
                    return left;
                }
                // 这个待删除的结点左子树和右子树都不为空，Hibbard Deletion
                // 找到当然root的后继结点，右子树的最小值结点
                Node successor = min(root.right);
                // 1.先在右子树中删除这个节点
                successor.right=removeMin(root.right);
                // 2.连接root.left
                successor.left=root.left;
                //gc
                root.left=root.right=root=null;
                return successor;
            }
        }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    /**
     * 按照先序遍历的方式，将BST的节点值存入到sb之中
     * @param root
     * @param height
     * @param sb
     */
    private void generateBSTString(Node root, int height, StringBuilder sb) {
        // 边界
        if (root == null) {
            sb.append(generateHeightStr(height)).append("NULL\n");
            return;
        }
        sb.append(generateHeightStr(height)).append(root.val).append("\n");
        // 递归打印左子树
        generateBSTString(root.left,height + 1,sb);
        generateBSTString(root.right,height + 1,sb);
    }

    /**
     * 按照当前节点的高度打印 --
     * root.left => --
     * 第二层 ----
     * @param height
     * @return
     */
    private String generateHeightStr(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}

class Node {
    int val;
    Node left;
    Node right;
    public Node(int val) {
        this.val = val;
    }
}